#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

#define true 1
#define false 0

//初始化
int LinkListInit(LinkList* list)
{
    list->head = (Node*)malloc(sizeof(Node));
    if(list->head == NULL)
    {
        printf("LinkListInit malloc error!\n");
        return false;
    }
    list->head->data = 0;
    list->head->next = NULL;
    list->len = 0;
    return true;
}

//创建节点
Node* CreateNode(ElementType element)
{
    Node* NewNode = (Node*) malloc(sizeof(Node));
    if(NewNode == NULL)
    {
        printf("CreateNode malloc error!\n");
        return NULL;
    } 
    NewNode->data = element;
    NewNode->next = NULL;
    return NewNode;
}

//尾插法
void LinkListInsertTail(LinkList* list, ElementType element)
{
    Node* NewNode = CreateNode(element);
    if(NewNode == NULL)
    {
        printf("inserttail CreateNode error!\n");
        return;
    }
    Node *cur = list->head;
    while(cur->next != NULL)
    {
        cur = cur->next;
    }
    cur->next = NewNode;
    list->len++;
}

//清空链表元素————将有效链表依次删除
void LinkListFree(LinkList* list)
{
    
    Node* cur;
    while(list->head->next != NULL)
    {
        //指针指向待删除节点地址
        cur = list->head->next;
        //贯穿
        list->head->next = cur->next;
        //释放cur节点
        free(cur);
        list->len--;
    }
}

//销毁链表
void LinkListDestroy(LinkList* list)
{
    LinkListFree(list);
    free(list->head);
    list->head = NULL;
}

bool IsEmpty(LinkList* list)
{
    return list->head->next == NULL;
}

//打印链表
void LinkListPrint(LinkList* list)
{
    printf("len: %d\n", list->len);
    Node* cur = list->head->next;
    while(cur != NULL)
    {
       printf("%d ", cur->data);
       cur = cur->next;
    }
    printf("\n");
}

//头插法
void InsertHead(LinkList* list, ElementType element)
{
    Node* NewNode = CreateNode(element);
    if(NewNode == NULL)
    {
        printf("inserttail CreateNode error!\n");
        return;
    }
    NewNode->next = list->head->next;
    list->head->next = NewNode;
    list->len++;
}

//指定下标位置插入
void LinkListInsertIndex(LinkList* list, ElementType element, int index)
{
    if(index < 0 || index > list->len)
    {
        printf("insertIndex invalid place!\n");
        return;
    }
    Node* NewNode = CreateNode(element);
    if(NewNode == NULL)
    {
        printf("insertIndex CreateNode error!\n");
        return;
    }
    Node* cur = list->head;
    //
    while(index != 0)
    {
        cur = cur->next;
        index--;
    }
    NewNode->next = cur->next;//先牵右手
    cur->next = NewNode;      //再牵左手
    list->len++;
}

//指定下标位置删除
void LinkListRemoeIndex(LinkList* list, int index)
{
    if(index < 0 || index >= list->len)
    {
        printf("RemoveIndex invalid place!\n");
        return;
    }
    Node* cur = list->head;
    while(index != 0)
    {
        cur = cur->next;
        index--;
    }
    Node* FreeNode = cur->next;// 记录要删除节点地址
    cur->next = FreeNode->next;//链接删除节点的前节点和后节点
    free(FreeNode);
    list->len--;
}

//按值删除
void LinkListRemoveByElement(LinkList* list, ElementType element)
{
    Node* cur = list->head;
    while(cur->next != NULL)
    {
       if(cur->next->data == element)
       {
          Node* FreeNode = cur->next;
          cur->next = FreeNode->next;
          free(FreeNode);
          list->len--;
       }
       else
       {
          cur = cur->next;
       }
    }
}

//按位置查找
ElementType* LinkListFindByIndex(LinkList* list, int index)
{
   if(index < 0 || index >= list->len)
    {
        printf("FindByIndex invalid place!\n");
        return NULL;
    } 
    Node* cur = list->head;
    while(index != 0)
    {
        cur = cur->next;
        index--;
    }
    return &cur->next->data;
}

//返回指定元素下标
int* LinkListFindByElement(LinkList* list, ElementType element)
{
    int* findVector = (int*)malloc(sizeof(int) * (list->len + 1));
    if(findVector == NULL)
    {
        printf("FindByElement malloc error!\n");
        return NULL;
    }
    Node* cur = list->head;
    int count = 0;
    int k = 0;
    while(cur->next != NULL)
    {
        if(cur->next->data == element)
        {
            findVector[k] = count;
            k++;
        }
        count++;
        cur = cur->next;
    }
    findVector[k] = -1;
    return findVector;
}

//按位置修改值
void LinkListSetValueByIndex(LinkList* list, ElementType element, int index)
{
    if(index < 0 || index >= list->len)
    {
        printf("SetValueByIndex invalid place!\n");
        return;
    } 
    Node* cur = list->head;
    while(index != 0)
    {
        cur = cur->next;
        index--;
    }
    cur->next->data = element;
}

//按值修改
void LinkListSetValueByElement(LinkList* list, ElementType oldValue, ElementType newValue)
{
    int* findVetor = LinkListFindByElement(list, oldValue);
    if(findVetor == NULL)
    {
        printf("can not find ele3ment!\n");
        return;
    }
    int* temp = findVetor;
    while(*temp != -1)
    {
        LinkListSetValueByIndex(list, newValue, *temp);
        temp++;
    }
    free(findVetor);
}

//冒泡排序
void LinkListBubbleSort(LinkList* list)
{
    for(int i = 0; i < list->len -1; i++)
    {
        //冒一趟，将一个最大数置于链表尾部，接着开始新一轮冒泡，结束位置是 list->len - i - 1
        Node * cur = list->head;
        for(int j = 0; j < list->len - i - 1; j++)
        {
            if(cur->next->data  >  cur->next->next->data)
            {
                Node* Prev = cur->next;
                Node* Next = cur->next->next;
                Prev->next = Next->next;
                Next->next = Prev;
                cur->next = Next;
            }
            cur = cur->next;
        }
    }
}

//链表逆序（循环）
void LinkListReserveList(LinkList* list)
{
    Node* Prev = NULL;
    Node* Cur = list->head->next;
    Node* Next = Cur->next;
    while(Next != NULL)
    {

        Cur->next = Prev;
        Prev = Cur;
        Cur = Next;
        Next = Cur->next;
    }
    Cur->next = Prev;
    list->head->next = Cur;
}

//链表逆序（递归）
//调用形式  list.head->next = ReserveList2(list.head->next)
Node* LinkListReserveList2(Node* node)
{   
    Node* tail;
    if(node->next != NULL)
    {
        tail = LinkListReserveList2(node->next);
        node->next->next = node;
        node->next = NULL;
        return tail;
    }
    return node;
}

//链表有序合并
LinkList* LinkListMergeList(LinkList* list1, LinkList* list2)
{
    LinkListBubbleSort(list1);
    LinkListBubbleSort(list2);

    LinkList* list3 = (LinkList*)malloc(sizeof(LinkList));
    if(list3 == NULL)
    {
        printf("MergeList malloc error!\n");
        return NULL;
    }
    LinkListInit(list3);
    Node* cur = list3->head;
    while(list1->head->next != NULL && list2->head->next != NULL)
    {
        if(list1->head->next->data  <  list2->head->next->data)
        {
            cur->next = list1->head->next;
            cur = cur->next;
            list3->len++;
            list1->head->next = list1->head->next->next;
        }
        else
        {
            cur->next = list2->head->next;
            cur = cur->next;
            list2->head->next = list2->head->next->next;   
        }   
    }

    if(list1->head->next != NULL)
    {
        cur->next = list1->head->next;
    }
    if(list2->head->next != NULL)
    {
        cur->next = list2->head->next;
    }
    
    list3->len = list1->len + list2->len;

    return list3;
}


LinkList * MergeList(LinkList *list1,LinkList *list2)
{
    LinkListBubbleSort(list1);
    LinkListBubbleSort(list2);

    //init list3
    struct LinkList* list3 = (struct LinkList* )malloc(sizeof(struct LinkList));
    if(list3 == NULL)
    {
        printf("MergeList malloc error!\n");
        return NULL;
    }
    LinkListInit(list3);


    struct Node *TravelPoint = list3->head;
    list1->head = list1->head->next;
    list2->head = list2->head->next;
    while(list1->head != NULL && list2->head != NULL)
    {
        if(list1->head->data < list2->head->data)
        {
            TravelPoint->next = list1->head;
            list1->head = list1->head->next;
            list3->len++;
        }
        else
        {
            TravelPoint->next = list2->head;
            list2->head = list2->head->next;
            list3->len++;
        }
        TravelPoint=TravelPoint->next;
    }

    if(list1->head!= NULL)
    {
        TravelPoint->next = list1->head;
        list3->len++;
    }

    if(list2->head != NULL)
    {
        TravelPoint->next = list2->head;
        list3->len++;
    }
    list3->len = list1->len + list2->len;
    return list3;
}




